Decision Trees for Uncertain Data.
Abstract—Traditional decision tree classifiers work with data whose values are known and precise. We extend such classifiers to handle data with uncertain information, which originates from measurement/quantisation errors, data staleness, multiple repeated measurements, etc. The value uncertaintyis represented by multiple values forming a probability distribution function (pdf). We discover that the accuracy of a decision tree classifier can be much improved if the whole pdf, rather than a simple statistic, is taken into account. We extend classical decision tree building algorithms to handle data tuples with uncertain values. Sinceprocessing pdf’sis computationally more costly, we propose a series of pruning techniques that can greatly improve the efficiency of the construction of decision trees. I.
Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space.

S%2DOLAP an OLAP system for analyzing sequence data.

Filtering Data Streams for Entity%2DBased Continuous Queries.
Abstract—The idea of allowing query users to relax their correctness requirements in order to improve performance of a data stream management system (e.g., location-based services and sensor networks) has been recently studied. By exploiting the maximum error (or tolerance) allowed in query answers, algorithms for reducing the use of system resources have been developed. In most of these works, however, query tolerance is expressed as a numerical value, which may be difficult to specify. We observe that in many situations, users may not be concerned with the actual value of an answer, but rather which object satisfies a query (e.g., “who is my nearest neighbor?”). In particular, an entity-based query returns only the names of objects that satisfy the query. For these queries, it is possible to specify a tolerance that is “non-value-based”. In this paper, we study fraction-based tolerance, a type of non-value-based tolerance, where a user specifies the maximum fractions of a query answer that can be false positives and false negatives. We develop fraction-based tolerance for two major classes of entitybased queries: (1) non-rank-based-query (e.g., range queries) and (2) rank-based-query (e.g., k-nearest-neighbor queries). These definitions provide users with an alternative to specify the maximum tolerance allowed in their answers. We further investigate how these definitions can be exploited in a distributed stream environment. We design adaptive filter algorithms that allow updates be dropped conditionally at the data stream sources without affecting the overall query correctness. Extensive experimental results show that our protocols reduce the use of network and energy resources significantly. Index Terms—data streams, continuous queries, adaptive filters, fraction-based tolerance I.
Clustering Uncertain Data Using Voronoi Diagrams and R%2DTree Index.
whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf’s, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organise the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods.
Efficient Skyline Evaluation over Partially Ordered Domains.
Although there has been a considerable body of work on skyline evaluation in multidimensional data with totally ordered attribute domains, there are only a few methods that consider attributes with partially ordered domains. Existing work maps each partially ordered domain to a total order and then adapts algorithms for totallyordered domains to solve the problem. Nevertheless these methods either use stronger notions of dominance, which generate false positives, or require expensive dominance checks. In this paper, we propose two new methods, which do not have these drawbacks. The first method uses an appropriate mapping of a partial order to a total order, inspired by the lattice theorem and an off-the-shelf skyline algorithm. The second technique uses an appropriate storage and indexing approach, inspired by column stores, which enables efficient verification of whether a pair of objects are incompatible. We demonstrate that both our methods are up to an order of magnitude more efficient than previous work and scale well with different problem parameters, such as complexity of partial orders.

Collaborative resource discovery in social tagging systems.


XML Data Integration Using Fragment Join.
Abstract. We study the problem of answering XML queries over multiple data sources under a schema-independent scenario where XML schemas and schema mappings are unavailable. We develop the fragment join operator — a general operator that merges two XML fragments based on their overlapping components. We formally define the operator and propose an efficient algorithm for implementing it. We define schema-independent query processing over multiple data sources and propose a novel framework to solve this problem. We provide theoretical analysis and experimental results that show that our approaches are both effective and efficient. 1
Decision Trees for Uncertain Data.
Abstract—Traditional decision tree classifiers work with data whose values are known and precise. We extend such classifiers to handle data with uncertain information, which originates from measurement/quantisation errors, data staleness, multiple repeated measurements, etc. The value uncertaintyis represented by multiple values forming a probability distribution function (pdf). We discover that the accuracy of a decision tree classifier can be much improved if the whole pdf, rather than a simple statistic, is taken into account. We extend classical decision tree building algorithms to handle data tuples with uncertain values. Sinceprocessing pdf’sis computationally more costly, we propose a series of pruning techniques that can greatly improve the efficiency of the construction of decision trees. I.
Naive Bayes Classification of Uncertain Data.

An Audit Environment for Outsourcing of Frequent Itemset Mining.
Finding frequent itemsets is the most costly task in association rule mining. Outsourcing this task to a service provider brings several benefits to the data owner such as cost relief and a less commitment to storage and computational resources. Mining results, however, can be corrupted if the service provider (i) is honest but makes mistakes in the mining process, or (ii) is lazy and reduces costly computation, returning incomplete results, or (iii) is malicious and contaminates the mining results. We address the integrity issue in the outsourcing process, i.e., how the data owner verifies the correctness of the mining results. For this purpose, we propose and develop an audit environment, which consists of a database transformation method and a result verification method. The main component of our audit environment is an artificial itemset planting (AIP) technique. We provide a theoretical foundation on our technique by proving its appropriateness and showing probabilistic guarantees about the correctness of the verification process. Through analytical and experimental studies, we show that our technique is both effective and efficient. 1.
Secure kNN computation on encrypted databases.
Service providers like Google and Amazon are moving into the SaaS (Software as a Service) business. They turn their huge infrastructure into a cloud-computing environment and aggressively recruit businesses to run applications on their platforms. To enforce security and privacy on such a service model, we need to protect the data running on the platform. Unfortunately, traditional encryption methods that aim at providing “unbreakable ” protection are often not adequate because they do not support the execution of applications such as database queries on the encrypted data. In this paper we discuss the general problem of secure computation on an encrypted database and propose a SCONEDB (Secure Computation ON an Encrypted DataBase) model, which captures the execution and security requirements. As a case study, we focus on the problem of k-nearest neighbor (kNN) computation on an encrypted database. We develop a new asymmetric scalar-product-preserving encryption (ASPE) that preserves a special type of scalar product. We use APSE to construct two secure schemes that support kNN computation on encrypted data; each of these schemes is shown to resist practical attacks of a different background knowledge level, at a different overhead cost. Extensive performance studies are carried out to evaluate the overhead and the efficiency of the schemes.
An Audit Environment for Outsourcing of Frequent Itemset Mining.
Finding frequent itemsets is the most costly task in association rule mining. Outsourcing this task to a service provider brings several benefits to the data owner such as cost relief and a less commitment to storage and computational resources. Mining results, however, can be corrupted if the service provider (i) is honest but makes mistakes in the mining process, or (ii) is lazy and reduces costly computation, returning incomplete results, or (iii) is malicious and contaminates the mining results. We address the integrity issue in the outsourcing process, i.e., how the data owner verifies the correctness of the mining results. For this purpose, we propose and develop an audit environment, which consists of a database transformation method and a result verification method. The main component of our audit environment is an artificial itemset planting (AIP) technique. We provide a theoretical foundation on our technique by proving its appropriateness and showing probabilistic guarantees about the correctness of the verification process. Through analytical and experimental studies, we show that our technique is both effective and efficient. 1.
Mining Order%2DPreserving Submatrices from Data with Repeated Measurements.
Order-preserving submatrices (OPSM’s) have been shown useful in capturing concurrent patterns in data when the relative magnitudes of data items are more important than their absolute values. To cope with data noise, repeated experiments are often conducted to collect multiple measurements. We propose and study a more robust version of OPSM, where each data item is represented by a set of values obtained from replicated experiments. We call the new problem OPSM-RM (OPSM with repeated measurements). We define OPSM-RM based on a number of practical requirements. We discuss the computational challenges of OPSM-RM and propose a generic mining algorithm. We further propose a series of techniques to speed up two timedominating components of the algorithm. We clearly show the effectiveness of our methods through a series of experiments conducted on real microarray data. 1
Clustering Uncertain Data Using Voronoi Diagrams.
whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf’s, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organise the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods.
A Decremental Approach for Mining Frequent Itemsets from Uncertain Data.

OLAP on sequence data.
Many kinds of real-life data exhibit logical ordering among their data items and are thus sequential in nature. However, traditional online analytical processing (OLAP) systems and techniques were not designed for sequence data and they are incapable of supporting sequence data analysis. In this paper, we propose the concept of Sequence OLAP, or S-OLAP for short. The biggest distinction of S-OLAP from traditional OLAP is that a sequence can be characterized not only by the attributes ’ values of its constituting items, but also by the subsequence/substring patterns it possesses. This paper studies many aspects related to Sequence OLAP. The concepts of sequence cuboid and sequence data cube are introduced. A prototype S-OLAP system is built in order to validate the proposed concepts. The prototype is able to support “pattern-based” grouping and aggregation, which is currently not supported by any OLAP system. The implementation details of the prototype system as well as experimental results are presented.
Adaptive Frequency Counting over Bursty Data Streams.

Adaptive Frequency Counting over Bursty Data Streams.

Mining Time%2DDelayed Associations from Discrete Event Datasets.

Reducing UK%2DMeans to K%2DMeans.

Mining Frequent Itemsets from Uncertain Data.
Abstract. We study the problem of mining frequent itemsets from uncertain data under a probabilistic framework. We consider transactions whose items are associated with existential probabilities and give a formal definition of frequent patterns under such an uncertain data model. We show that traditional algorithms for mining frequent itemsets are either inapplicable or computationally inefficient under such a model. A data trimming framework is proposed to improve mining efficiency. Through extensive experiments, we show that the data trimming technique can achieve significant savings in both CPU cost and I/O cost. 1
Security in Outsourcing of Association Rule Mining.

On mining micro%2Darray data by Order%2DPreserving Submatrix.
We study the problem of pattern-based subspace clustering. Unlike traditional clustering methods that focus on grouping objects with similar values on a set of dimensions, clustering by pattern similarity finds objects that exhibit a coherent pattern of rises and falls in subspaces. Applications of pattern-based subspace clustering include DNA micro-array data analysis, automatic recommendation systems and target marketing systems. Our goal is to devise pattern-based clustering methods that are capable of (1) discovering useful patterns of various shapes, and (2) discovering all significant patterns. We argue that previous solutions in pattern-based subspace clustering do not satisfy both requirements. Our approach is to extend the idea of Order-Preserving Submatrix (or OPSM). We devise a novel algorithm for mining OPSM, show that OPSM can be generalized to cover most existing pattern-based clustering models, and propose a number of extension to the original OPSM model.
Mining periodic patterns with gap requirement from sequences.
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l, we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length-l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement. That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem, and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study. 1
Efficient Clustering of Uncertain Data.

Uncertain Data Mining An Example in Clustering Location Data.
Abstract. Data uncertainty is an inherent property in various applications due to reasons such as outdated sources or imprecise measurement. When data mining techniques are applied to these data, their uncertainty has to be considered to obtain high quality results. We present UK-means clustering, an algorithm that enhances the K-means algorithm to handle data uncertainty. We apply UKmeans to the particular pattern of moving-object uncertainty. Experimental results show that by considering uncertainty, a clustering algorithm can produce more accurate results. 1
On Mining Micro%2Darray data by Order%2DPreserving Submatrix.
We study the problem of pattern-based subspace clustering. Unlike traditional clustering methods that focus on grouping objects with similar values on a set of dimensions, clustering by pattern similarity finds objects that exhibit a coherent pattern of rises and falls in subspaces. Applications of pattern-based subspace clustering include DNA micro-array data analysis, automatic recommendation systems and target marketing systems. Our goal is to devise pattern-based clustering methods that are capable of (1) discovering useful patterns of various shapes, and (2) discovering all significant patterns. We argue that previous solutions in pattern-based subspace clustering do not satisfy both requirements. Our approach is to extend the idea of Order-Preserving Submatrix (or OPSM). We devise a novel algorithm for mining OPSM, show that OPSM can be generalized to cover most existing pattern-based clustering models, and propose a number of extension to the original OPSM model.
Mining Periodic Patterns with Gap Requirement from Sequences.
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l, we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length-l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement. That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem, and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study. 1
Online Algorithms for Mining Inter%2Dstream Associations from Large Sensor Networks.
We study the problem of mining frequent value sets from a  large sensor network. We discuss how sensor stream data could be represented  that facilitates e#cient online mining and propose the interval-list  representation. Based on Lossy Counting, we propose ILB, an intervallist  -based online mining algorithm for discovering frequent sensor value  sets. Through extensive experiments, we compare the performance of ILB  against an application of Lossy Counting (LC) using a weighted transformation  method. Results show that ILB outperforms LC significantly  for large sensor networks.
Mining Periodic Patterns with Gap Requirement from Sequences.
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l, we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length-l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement. That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem, and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study. 1
Adaptive Stream Filters for Entity%2Dbased Queries with Non%2DValue Tolerance.
We study the problem of applying adaptive filters for approximate query processing in a distributed stream environment. We propose filter bound assignment protocols with the objective of reducing communication cost. Most previous works focus on value-based queries (e.g., average) with numerical error tolerance. In this paper, we cover entity-based queries (e.g., a nearest neighbor query returns object names rather than a single value). In particular, we study non-value-based tolerance (e.g., the answer to the nearest-neighbor query should rank third or above). We investigate different non-value-based error tolerance definitions and discuss how they are applied to two classes of entity-based queries: non-rankbased and rank-based queries. Extensive experiments show that our protocols achieve significant savings in both communication overhead and server computation. 1
Indexing Multi%2DDimensional Uncertain Data with Arbitrary Probability Density Functions.
In an “uncertain database”, an object o is associated with a multi-dimensional probability density function (pdf), which describes the likelihood that o appears at each position in the data space. A fundamental operation is the “probabilistic range search ” which, given a value pq and a rectangular area rq, retrieves the objects that appear in rq with probabilities at least pq. In this paper, we propose the U-tree, an access method designed to optimize both the I/O and CPU time of range retrieval on multi-dimensional imprecise data. The new structure is fully dynamic (i.e., objects can be incrementally inserted/deleted in any order), and does not place any constraints on the data pdfs. We verify the query and update efficiency of U-trees with extensive experiments. 1
Efficient Algorithms for Mining and Incremental Update of Maximal Frequent Sequences.

Subsampled Model Aggregation.

SF%2DTree An Efficient and Flexible Structure for Estimating Selectivity of Simple Path Expressions with Statistical Accuracy Guarantee.

Optimization in Data Cube System Design.
Abstract. The design of an OLAP system for supporting real-time queries is one of the major research issues. One approach is to use data cubes, which are materialized precomputed multidimensional views of data in a data warehouse. We can derive a set of data cubes to answer each frequently asked query directly. However, there are two practical problems: (1) the maintenance cost of the data cubes, and (2) the query cost to answer those queries. Maintaining a data cube requires disk storage and CPU computation, so the maintenance cost is related to the total size as well as the total number of data cubes materialized. In most cases, materializing all data cubes is impractical. The maintenance cost may be reduced by merging some data cubes. However, the resulting larger data cubes will increase the query cost of answering some queries. If the bounds on the maintenance cost and the query cost are too strict, we help the user decide which queries to be sacrificed and not taken into consideration. We have defined an optimization problem in data cube system design. Given a maintenance-cost bound, a query-cost bound and a set of frequently asked queries, it is necessary to determine a set of data cubes such that the system can answer a largest subset of the queries without violating the two bounds. This is an NP-hard problem. We propose approximate Greedy algorithms GR, 2GM and 2GMM, which are shown to be both effective and efficient by experiments done on a census data set and a forest-cover-type data set.
Mining Emerging Substrings.
We introduce a new type of KDD patterns called emerging substrings. In a sequence database, an emerging substring (ES) of a data class is a substring which occurs more frequently in that class rather than in other classes. ESs are important to sequence classification as they capture significant contrasts between data classes and provide insights for the construction of sequence classifiers. We propose a suffix tree-based framework for mining ESs, and study the effectiveness of applying one or more pruning techniques in different stages of our ES mining algorithm. Experimental results show that if the target class is of a small population with respect to the whole database, which is the normal scenario in single-class ES mining, most of the pruning techniques would achieve considerable performance gain.
Maintenance of Partial%2DSum%2DBased Histograms.
This paper introduces an efficient method for the maintenance of wavelet-based histograms built on partial sums. Wavelet-based histograms can be constructed from either raw data distributions or partial sums. The two construction methods have their own merits. Previous works have only focused on the maintenance of raw-data-based histograms. However, it is highly inefficient to apply directly their techniques to partial-sum-based histograms because a single data update would trigger changes of multiple partial sums, which in turn, would trigger large amounts of computation on the changes of the wavelet decomposition.
Maintaining Temporal Consistency of Discrete Objects in Soft Real%2DTime Database Systems.
A real-time database system contains base data items which record and model a physical, real world environment. For better decision support, base data items are summarized and correlated to derive views. These base data and views are accessed by application transactions to generate the ultimate actions taken by the system. As the environment changes, updates are applied to base data, which subsequently trigger view recomputations. There are thus three types of activities: base data update, view recomputation, and transaction execution. In a real-time database system, two timing constraints need to be enforced. We require transactions meet their deadlines (transaction timeliness) and read fresh data (data timeliness). In this paper we define the concept of absolute and relative temporal consistency from the perspective of transactions for discrete data objects. We address the important issue of transaction scheduling among the three types of activities such that the two timing requirements can be met. We also discuss how a real-time database system should be designed to enforce different levels of temporal consistency.
A Comparison Study on Algorithms for Incremental Update of Frequent Sequences.

Efficient Algorithms for Incremental Update of Frequent Sequences.
Agrawal and Srikant first put forward the problem of mining frequently occurring se-  quences from a customer database [1]. In their model, a customer database consists of a set  of sequences. Each sequence is a chronologically ordered set of transactions (or itemsets).
An Efficient Algorithm for Incremental Update of Concept Spaces.
The vocabulary problem in information retrieval arises be-  cause authors and indexers often use different terms for the same con-  cept. A thesaurus defines mappings between different but related terms.
A lattice%2Dbased approach for I%2FO efficient association rule mining.



FFS %2D An I%2FO%2DEfficient Algorithm for Mining Frequent Sequences.

Efficient Algorithms for Concept Space Construction.
The vocabulary problem in information retrieval arises because  authors and indexers often use different terms for the same concept.
Updates and View Maintenance.
A database system contains base data items which record and model a physical, real  world environment. For better decision support, base data items are summarized and correlated  to derive views. These base data and views are accessed by application transactions to  generate the ultimate actions taken by the system. As the environment changes, updates are  applied to the base data, which subsequently trigger view recomputations. There are thus  three types of activities: base data update, view recomputation, and transaction execution.  In a real-time system, two timing constraints need to be enforced. We require transactions  meet their deadlines (transaction timeliness) and read fresh data (data timeliness). In this  paper we define the concept of absolute and relative temporal consistency from the perspective  of transactions. We address the important issue of transaction scheduling among the  three types of activities such that the two timing requirements can be met. We also discuss...
Prototypes Programmed Stock Trading.

Disk Scheduling.
Since the invention of the movable head disk, people have improved I/O performance by intelligent scheduling of disk accesses. We have applied these techniques to systems with large memories and potentially long disk queues. By viewing the entire buffer cache as a write buffer, we can improve disk bandwidth utilization by applying some traditional disk scheduling techniques. We have analyzed these techniques, which attempt to optimize head movement and guarantee fairness in response time, in the presence of long disk queues. We then propose two algorithms which take rotational latency into account, achieving disk bandwidth utilizations of nearly four times a simple first come first serve algorithm. One of these two algorithms, a weighted shortest total time first, is particularly applicable to a file server environment because it guarantees that all requests get to disk within a specified time window. 1.
Towards the building of a dense%2Dregion%2Dbased OLAP system.
On-line Analytical Processing (OLAP) has become a very useful tool in decision support  systems built on data warehouses. ROLAP (Relational OLAP) and MOLAP (Multidimensional  OLAP) are two popular approaches for building OLAP systems. These two  approaches have very different performance characteristics: MOLAP has good query performance  but bad space efficiency, while ROLAP can be built on mature RDBMS technology  but it needs sizable indices to support it. Many data warehouses contain many small clustered  multidimensional data (dense regions), with sparse points scattered around in the  rest of the space. For these databases, we propose that the dense regions be located and  separated from the sparse points. The dense regions can subsequently be represented by  small MOLAPs, while the sparse points are put in a ROLAP table. Thus the MOLAP  and ROLAP approaches can be integrated in one structure to build a high performance  and space efficient dense-region-based data cube. In this pa...
Selection of Melody Lines for Music Databases.

Exploiting the Duality of Maximal Frequent Itemsets and Minimal Infrequent Itemsets for I%2FO Efficient Association Rule Mining.

A Study on N%2DGram Indexing of Musical Features.

Text%2DSource Discovery and GlOSS Update in a Dynamic Web.

An Optimization Problem in Data Cube System Design.
. In an OLAP system, we can use data cubes (precomputed  multidimensional views of data) to support real-time queries.  To reduce the maintenance cost, which is related to the number  of cubes materialized, some cubes can be merged, but the resulting  larger cubes will increase the response time of answering some  queries. In order to satisfy the maintenance bound and response  time bound given by the user, we may have to sacrifice some of  the queries and not to take them into our consideration. The optimization  problem in the data cube system design is to optimize  an initial set of cubes such that the system can answer a maximum  number of queries and satisfy the bounds. This is an NP-complete  problem. Approximate algorithms Greedy Removing and 2-Greedy  Merging are proposed. Experiments have been done on a census  database and the results show that our approach is both effective  and efficient.  1 Introduction  1.1 DSS and OLAP  With the advancement of data warehousing technology...
Modeling splice sites with Bayes networks.

Requirement%2DBased Data Cube Schema Design.%2
On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically. A very important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation algorithm cMP and its variants. Algorithm cMP consists of two phases. In the first phase, an initial schema consisting of all the cubes required to efficiently answer the user queries is formed. In the second phase, cubes in the initial schema are selectively merged to satisfy the memory constraint. We show that cMP is very effective in prunning the search space ...
Anchor point indexing in Web document retrieval.
Traditional WWW search engines, such as Alta Vista, index and recommend individual  Web pages to assist users in locating relevant documents. As the Web grows, however, the  number of matching pages increases at a tremendous rate. Users are often overwhelmed by  the large answer set recommended by the search engines. Also, if a matching document is  a hypertext, the document structure is destroyed and the individual pages that compose  the document are returned instead. The logical starting point of the hyper-document is  thus hidden among the large basket of matching pages. Users need to spend a lot of effort  browsing through the pages to locate the starting point, a very time consuming process.  This paper studies the anchor point indexing problem. The set of anchor points of a given  user query is a small set of key pages from which the larger set of documents that are relevant  to the query can be easily reached. The use of anchor points help solve the problems of huge  answer set...
Requirement%2DBased Data Cube Schema Design.%2
On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically. A very important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation algorithm cMP and its variants. Algorithm cMP consists of two phases. In the first phase, an initial schema consisting of all the cubes required to efficiently answer the user queries is formed. In the second phase, cubes in the initial schema are selectively merged to satisfy the memory constraint. We show that cMP is very effective in prunning the search space ...
Updates and View Maintenance in Soft Real%2DTime Database Systems.
A database system contains base data items which record and model a physical, real  world environment. For better decision support, base data items are summarized and correlated  to derive views. These base data and views are accessed by application transactions to  generate the ultimate actions taken by the system. As the environment changes, updates are  applied to the base data, which subsequently trigger view recomputations. There are thus  three types of activities: base data update, view recomputation, and transaction execution.  In a real-time system, two timing constraints need to be enforced. We require transactions  meet their deadlines (transaction timeliness) and read fresh data (data timeliness). In this  paper we define the concept of absolute and relative temporal consistency from the perspective  of transactions. We address the important issue of transaction scheduling among the  three types of activities such that the two timing requirements can be met. We also discuss...
A Study of Musical Features for Melody Databases.
Music has an auditory and temporal nature. The same piece can be interpreted in multiple, and often unrelated ways. Together with the limitations of its representations, the design of content-based music retrieval systems on the Web is a challenge. Most literatures on the problem map the problem to existing information retrieval paradigms, mainly that of text, by modelling music as a sequence of features [Lin77][MS90]. However, this mapping raises issues to be solved. Through the study of the statistical properties of six features including Profile, Note Duration Ratio Sequence, Interval Sequence and their variants, we answer four important questions that arises from mapping. These include the number of musical &#034;alphabets&#034; and &#034;words&#034;, whether Zipf&#039;s law holds for musical features, whether there are any musical &#034;stopwords&#034;, and the range of n for n-gram based music indices. The answers to these questions will affect crucial parameters in music retrieval systems, and whether the mapping...
DROLAP %2D A Dense%2DRegion Based Approach to On%2DLine Analytical Processing.
ROLAP (Relational OLAP) and MOLAP (Multidimensional OLAP) are two opposing techniques for building On-line Analytical Processing (OLAP) systems. MOLAP has good query performance but suffers when the data distribution in the multidimensional data cube is sparse. ROLAP can be built on mature RDBMS technology but its performance is not as competitive. Many data warehouses contain sparse but clustered multidimensional data. We propose a dense-region-based OLAP (DROLAP) system which surpasses both ROLAP and MOLAP in space efficiency and query performance. DROLAP applies the MOLAP approach on the dense regions discovered in the data, and handles the remaining small percentage of sparse points with the ROLAP approach. The core of building a DROLAP system lies in the mining of dense regions in a data cube. We have defined the dense region mining problem as an optimization problem. We show that conventional clustering techniques are not suitable for this problem, and have developed an efficient...
A Fast Algorithm for Density%2DBased Clustering in Large Database.

LGen %2D A Lattice%2DBased Candidate Set Generation Algorithm for I%2FO Efficient Association Rule Mining.
Most algorithms for association rule mining are variants of the basic Apriori algorithm  [1]. One characteristic of these Apriori-based algorithms is that candidate itemsets are  generated in rounds, with the size of the itemsets incremented by one per round. The  number of database scans required by Apriori-based algorithms thus depends on the size of  the largest large itemsets. In this paper we devise a more general candidate set generation  algorithm, LGen, which generates candidate itemsets of multiple sizes during each database  scan. We show that, given a reasonable set of suggested large itemsets, LGen can significantly  reduce the number of I/O passes required. In the best cases, only two passes are sufficient  to discover all the large itemsets irrespective of the size of the largest ones.  Keywords: Data mining, association rules, lattice, Apriori, LGen  1 Introduction  Data mining has recently attracted considerable attention from database practitioners and researchers beca...
Priority Scheduling of Transactions in Distributed Real%2DTime Databases.

Indexing Multilingual Information on the Web.

Recommending Anchor Points in Structure%2DPreserving Hypertext Document Retrieval.

Is Sampling Useful in Data Mining%3F A Case in the Maintenance of Discovered Association Rules.
By nature, sampling is an appealing technique for data mining, because approximate solutions in most cases may already be of great satisfaction to the need of the users. We attempt to use sampling techniques to address the problem of maintaining discovered association rules. Some studies have been done on the problem of maintaining the discovered association rules when updates are made to the database. All proposed methods must examine not only the changed part but also the unchanged part in the original database, which is very large, and hence take much time. Worse yet, if the updates on the rules are performed frequently on the database but the underlying rule set has not changed much, then the effort could be mostly wasted. In this paper, we devise an algorithm which employs sampling techniques to estimate the difference between the association rules in a database before and after the database is updated. The estimated difference can be used to determine whether we should update the...
An analysis of lock%2Dbased and optimistic concurrency control protocols in multiprocessor real%2Dtime databases.

Discovering user access patterns on the World Wide Web.
this paper, we focus on the techniques in designing a level 4 Web tool. A system design and its architecture is proposed. In particular, we study the problem of constructing user profiles from user access history.
A General Incremental Technique for Maintaining Discovered Association Rules.
A more general incremental updating technique is developed for maintaining the association rules discovered in a database in the cases including insertion, deletion, and modification of transactions in the database. A previously proposed algorithm FUP can only handle the maintenance problem in the case of insertion. The proposed algorithm FUP2 makes use of the previous mining result to cut down the cost of finding the new rules in an updated database. In the insertion only case, FUP2 is equivalent to FUP. In the deletion only case, FUP2 is a complementary algorithm of FUP which is very efficient when the deleted transactions is a small part of the database, which is the most applicable case. In the general case, FUP2 can efficiently update the discovered rules when new transactions are added to a transaction database, and obsolete transactions are removed from it. The proposed algorithm has been implemented and its performance is studied and compared with the best algorithms for mining...
Intelligent Agents for Matching Information Providers and Consumers on the World%2DWide%2DWeb.

Deadline Assignment in a Distributed Soft Real%2DTime System.
In a distributed environment, tasks often have processing demands on multiple different sites. A distributed task is usually divided up into several subtasks, each one to be executed at some site in order. In a real-time system, an overall deadline is usually specified by an application designer indicating when a distributed task is to be finished. However, the problem of how a global deadline is automatically translated to the deadline of each individual subtask has not been well studied. This paper examines (through simulations) four strategies for subtask deadline assignment in a distributed soft real-time environment.  Keywords: soft real-time, distributed systems, deadline assignment, scheduling. 1 Introduction Consider a radar surveillance system whose task is to track flying objects, decide whether an object is friendly or hostile, and in the latter case, come up with a combat strategy. This system requires the cooperation of several different components: a radar sensor componen...
Database Support for Efficiently Maintaining Derived Data.
Derived data is maintained in a database system to correlate and summarize base data which record real world facts. As base data changes, derived data needs to be recomputed. A high performance system should execute all these updates and recomputations in a timely fashion so that the data remains fresh and useful, while at the same time executing user transactions quickly. This paper studies the intricate balance between recomputing derived data and transaction execution. Our focus is on efficient recomputation strategies --- how and when recomputations should be done to reduce their cost without jeopardizing data timeliness. We propose the Forced Delay recomputation algorithm and show how it can exploit update locality  to improve both data freshness and transaction response time.  Keywords: derived data, view maintenance, active database system, transaction scheduling, update locality. 1 Introduction  Active rule-based systems are often employed in dynamic environments to monitor the...
Impact of priority assignment on optimistic concurrency control in distributed real%2Dtime databases.
In the studies of real-time concurrency control protocols (RT-CCPs), it is always assumed that earliest deadline first (EDF) is employed as the CPU scheduling algorithm. However, using purely (ultimate) deadline for priority assignment may not be suitable for distributed real-time database systems (DRTDBS) in which there exist different kinds of transactions, such as global and local transactions. In order to improve the performance, different priority assignment heuristics have to be used. In this paper, we have investigated the performance of dvferent priori &amp; assignment heuristics for sub-transactions in DRTDBS with optimistic concurrency control (OCC) protocol. It is found that the heuristics, which are suitable for distributed real-time systems, are not suitable for DRTDBS. We $nd that our proposed heuristic, which considers both deadline constraint and data contention, can give the best performance. 1
Priority Assignment for Sub%2Dtransaction in Distributed Real%2Dtime Databases.
Recent studies on deadline assignment to sub-tasks in distributed real-time systems have suggested different heuristics for priority assignment to improve the system performance [6,10]. These heuristics only consider the real-time constraints of the tasks and may not be suitable for distributed real-time database systems (DRTDBS). In this paper, we examine the performance of these heuristics for DRTDBS and suggest better alternatives. Our performance results show that many factors, such as data conflict resolution, transaction aborts and restarts, that are unique to a database system in fact have significant impact on the performance of the heuristics for subtransaction priority assignment. One of our proposed heuristics, which considers both real-time constraints of the transactions and the impact on data contention, gives the best performance.  1 Introduction  Transactions in a distributed real-time database system (DRTDBS) have constraints on their completion times which are usually...
Scheduling Soft Real%2DTime Jobs Over Dual Non%2DReal%2DTime Servers.

Overview of the STanford Real%2Dtime Information Processor %28STRIP%29.
We believe that the greatest growth potential for soft realtime databases is not as isolated monolithic databases but as components in open systems consisting of many heterogeneous databases. In such environments, the flexibility to deal with unpredictable situations and the ability to cooperate with other databases (often non-real-time databases) is just as important as the guarantee of stringent timing constraints. In this paper, we describe a database designed explicitly for heterogeneous environments, the STanford Realtime Information Processor (STRIP). STRIP, which runs on standard Posix Unix, is a soft real-time main memory database with special facilities for importing and exporting data as well as handling derived data. We will describe the architecture of STRIP, its unique features, and its potential uses in overall system architectures. 1 Project Goals  The STanford Real-time Information Processor (STRIP) was designed with the following goals: 1. support for transactions and ...
Applying Update Streams in a Soft Real%2DTime Database System.
Many papers have examined how to efficiently export a materialized view but to our knowledge none have studied how to efficiently import one. To import a view, i.e., to install a stream of updates, a real-time database system must process new updates in a timely fashion to keep the database &#034;fresh,&#034; but at the same time must process transactions and ensure they meet their time constraints. In this paper, we discuss the various properties of updates and views (including staleness) that affect this tradeoff. We also examine, through simulation, four algorithms for scheduling transactions and installing updates in a soft real-time database.  Keywords: soft real-time, temporal databases, materialized views, updates.  1 Introduction  The problem we study in this paper arose during the ongoing implementation of the STRIP real-time database system.  1  This system [2] provides traditional database services (e.g., SQL, indexing, recovery) with real-time facilities (e.g., transaction deadlines,...
Subtask Deadline Assignment for Complex Distributed Soft Real%2DTime Tasks.
Complex distributed tasks often involve parallel execution of subtasks at different nodes. To meet the deadline of a global task, all of its parallel subtasks have to be finished on time. Comparing to a local task (which involves execution at only one node), a global task may have a much harder time making its deadline because it is fairly likely that at least one of its subtasks run into an overloaded node. Another problem with complex distributed tasks occurs when a global task consists of a number of serially executing subtasks. In this case, we have the problem of dividing up the end-to-end deadline of the global task and assigning them to the intermediate subtasks. In this paper, we study both of these problems. Different algorithms for assigning deadlines to subtasks are presented and evaluated.  Keywords: soft real-time, distributed systems, parallel systems, deadline assignment, scheduling. 1 Introduction  In traditional soft real-time applications, a task is considered a singl...
Emulating Soft Real%2DTime Scheduling Using Traditional Operating System Schedulers.
Real-time scheduling algorithms are usually only available in the kernels of real-time operating systems, and not in more general purpose operating systems, like Unix. For some soft real-time problems, a traditional operating system may be the development platform of choice. This paper addresses methods of emulating real-time scheduling algorithms on top of standard time-share schedulers. We examine (through simulations) three strategies for priority assignment within a traditional multi-tasking environment. The results show that the emulation algorithms are comparable in performance to the real-time algorithms and in some instances outperform them. Keywords: soft real-time, priority assignment, scheduling. 1 Introduction Consider program trading, the use of computer programs to initiate trades in a financial market with little or no human intervention [Voe87]. A financial market (e.g., a stock market) is a complex process whose state is partially captured by variables such a...
Aggressive Transmissions of Short Messages Over Redundant Paths.

Deadline Assignment in a Distributed Soft Real%2DTime System.
In a distributed environment, tasks often have processing demands on multiple different sites. A distributed task is usually divided up into several subtasks, each one to be executed at some site in order. In a real-time system, an overall deadline is usually specified by an application designer indicating when a distributed task is to be finished. However, the problem of how a global deadline is automatically translated to the deadline of each individual subtask has not been well studied. This paper examines (through simulations) four strategies for subtask deadline assignment in a distributed soft real-time environment.  Keywords: soft real-time, distributed systems, deadline assignment, scheduling. 1 Introduction Consider a radar surveillance system whose task is to track flying objects, decide whether an object is friendly or hostile, and in the latter case, come up with a combat strategy. This system requires the cooperation of several different components: a radar sensor componen...
The Gold Mailer.
The goal of the Gold project is to implement a set of tools to interoperate with unstructured and semistructured data and services. We have selected the electronic mail domain ad the first scenario in which to implement and demonstrate some of the tools. This paper describes the Gold Mailer, a system that provides wers with an integrated way to send and receive messages wing different media (e-mail, fozes, phones), eficiently store and retrieve these messages, and access a variety of sources of other weful information. Our mailer solves the problems of information overload, Organization of messages and multiple interfaces. By providing good storage and retrieval facilities, it can be wed ad a powerful information processing engine covering a range of weful office information. Unlike some recent research efforta ([Ter90, KT088, LYY891) which have implemented mailers with relational-like query facilities, the Gold mailer provides a database system interface that fits more naturally. This document ezplains the current implementation of the Gold mailer. 1
Third Generation TP Monitors A Database Challenge.

Aggressive transmissions over redundant paths.

